package com.hdu.other.unionSet;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class lc2092 {

    class Solution {

        int[] father;
        boolean[] know;

        public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
            build(n, firstPerson);
            int len = meetings.length;
            Arrays.sort(meetings, Comparator.comparingInt(a -> a[2]));
            int cur = 0;
            while (cur < len) {
                int startIndex = cur;
                while (cur + 1 < len && meetings[cur][2] == meetings[cur + 1][2]) {
                    cur++;
                }
                for (int i = startIndex; i <= cur; i++) {
                    union(meetings[i][0], meetings[i][1]);
                }
                for (int i = startIndex; i <= cur; i++) {
                    int a = meetings[i][0];
                    int b = meetings[i][1];
                    if (!know[find(a)]) {
                        father[a] = a;
                    }
                    if (!know[find(b)]) {
                        father[b] = b;
                    }
                }
                cur++;
            }
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (know[find(i)]) {
                    res.add(i);
                }
            }
            return res;
        }


        void build(int n, int firstPerson) {
            father = new int[n];
            know = new boolean[n];
            Arrays.fill(know, false);
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
            father[firstPerson] = 0;
            know[0] = true;
        }

        int find(int num) {
            if (father[num] != num) {
                father[num] = find(father[num]);
            }
            return father[num];
        }

        void union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fx != fy) {
                father[fx] = fy;
                know[fy] |= know[fx];
            }
        }
    }
}
